返回

转到题目

思路1:

我们读题知:我们要找到无根树中有多少 符合条件 的简单路径 我们第一直觉肯定是在树的整体上看，但是很不好。 每个两个节点之间都必定有且唯一有一条简单路径，因此这种普通枚举方法非常耗时。$O(n^2)$ 因为我们很难快速枚举所有路径，因此我们应该换种思考方式。

• 着重于怎么枚举更简单、快速:
  • 我们知道所有顶点作为LCA对应的路径集,他们并集就是所有 简单路径，交集是空集 换句话说,每个点作为LCA对应的路径集都是互斥且完备的
  • 也正是因为其 互斥且完备 的性质，我们可以将问题分解成独立的子问题 子问题之间(父子)又有可能存在偏序关系 状态之间是DP来转移

考虑到这，我们的枚举路径的问题差不多解决了，但是路径的 合法性 怎么检查?

题目要求可以转化为: 路径中至少存在一个节点要小于a,且至少存在一个节点要大于b 对于这种条件，我们直观的想法是根据枚举直接检查，但是这种路径检查，大案例时会较慢 : $O(L)$ 我们可想到，用贪心思想优化一下,满足条件的路径，其拓展，也一定是满足的 或者从前后缀上讲,用前缀表(变化过程)来记录。快速得到 同性质区间 而前缀表体现在树上，就要思考一下，怎么样合并. 而每个父节点又有与某个指向节点具有 偏序关系，这样他们状态之间的转移就是乘法原理

到这里,问你就整体地解决了这个路径问题，利用了LCA来分离状态集转移、前缀来优化了路径合法性检查，使得$O(n^2 *L)$ -> $O(n)$Q